2941. Dima and array

Mother presented Dima an array of length n. This array is not simple, but special. Dima can choose two numbers i and d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), and the element at index i magically becomes equal to d. Dima plays with his array, and from time to time Mom asks him questions – what is the sum of all numbers in the array with indices from f to t inclusive? Dima easily handled these questions. Can you?

Input. The first line contains two integers n and q (1 ≤ n ≤ 5·10⁵, 1 ≤ q ≤ 10⁵) – the number of elements in the array and the total number of operations. The next line contains n integers: a₁, a₂, ..., a_n (-1000 ≤ a_i ≤ 1000) representing the initial state of the array. The following q lines contain operations and queries. The first character of each line can be either = or ?. If the line starts with =, it is an assignment operation, followed by i and d, which satisfy the constraints described earlier. If the line starts with ?, it is a query, followed by f and t (1 ≤ f, t ≤ n).

Output. For each query print on a separate line the sum of the numbers in the array with indexes from f to t inclusively.

Sample input	Sample output
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3	6 5

SOLUTION

data structures – segment tree

Algorithm analysis

To solve the problem, you should implement a segment tree that supports the modification of a single element and sum queries.

Example

Let’s simulate the queries provided in the example.

Algorithm realization

Store the segment tree in a vector called SegTree with a length of 4*MAX, where MAX is the maximum number of elements that can be stored in a segment.

#define MAX 500000

vector<int> SegTree(4*MAX,0);

The BuildTree function takes an array a, the current node number v, and the segment boundaries lpos and rpos as inputs to construct the segment tree.

void BuildTree(vector<int>&a, int v, int lpos, int rpos)

{

If the vertex v corresponds to a segment consisting of a single element (lpos equals rpos), then we have reached a leaf node of the segment tree. Assign the value a_lpos to this leaf node.

if (lpos == rpos) SegTree[v] = a[lpos];

else

{

Find the midpoint of the segment by calculating mid = (lpos + rpos) / 2.

int mid = (lpos + rpos) / 2;

Split the range [left; right] into [left; mid] and [mid + 1; right]. Then recursively construct segment tree on the subsegments.

BuildTree(a, 2*v, lpos, mid);

BuildTree(a, 2*v+1, mid + 1, rpos);

Recalculate the value of the sum in the current vertex of the segment tree.

SegTree[v] = SegTree[2*v] + SegTree[2*v+1];

}

}

The Update function assigns the value val to the element with the index pos.

The vertex v corresponds to the segment [lpos; rpos].

void Update(int v, int lpos, int rpos, int pos, int val)

{

If the vertex v corresponds to a segment consisting of a single element (lpos equals rpos), then we have reached a leaf node of the segment tree. Assign the value val to this leaf node.

if (lpos == rpos) SegTree[v] = val;

else

{

Otherwise, we calculate whether the element with index pos lies in the left or right child of vertex v. Run recursively its modification.

int mid = (lpos + rpos) / 2;

if (pos <= mid)

Update (2*v, lpos, mid, pos, val);

else

Update (2*v+1, mid+1, rpos, pos, val);

Recalculate the value of the sum in the current vertex of the segment tree.

SegTree[v] = SegTree[2*v] + SegTree[2*v+1];

}

}

The Summa function returns the value of the sum on the segment [left; right].

The vertex v corresponds to the segment [lpos; rpos].

int Summa(int v, int lpos, int rpos, int left, int right)

{

if (left > right) return 0;

If the range [left; right] coincides with the segment [lpos; rpos] stored in vertex v of the tree, then return the sum value stored in that node.

if ((left == lpos) && (right == rpos))

return SegTree[v];

Find the midpoint of the segment by calculating mid = (lpos + rpos) / 2.

int mid = (lpos + rpos) / 2;

Split the range [left; right] into [left; mid] and [mid + 1; right]. Then recursively compute the sum on the subsegments. Finally, add the obtained sums together.

return Summa(2*v, lpos, mid, left, min(right,mid)) +

Summa(2*v+1, mid+1, rpos, max(left,mid+1), right);

}

The main part of the program. Read the input data.

scanf("%d %d\n",&n,&q);

v.resize(n+1);

for(i = 1; i <= n; i++) scanf("%d",&v[i]); scanf("\n");

Construct a segment tree from array v.

BuildTree(v,1,1,n);

Sequentially process q queries. Depending on the type of each query, either perform element modification or calculate the sum on a segment.

for(j = 0; j < q; j++)

{

scanf("%c ",&c);

if (c == '=')

{

scanf("%d %d\n",&i,&d);

update(1,1,n,i,d);

} else

{

scanf("%d %d\n",&f,&t);

printf("%d\n",Summa(1,1,n,f,t));

}

}

Algorithm realization – iostream

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> SegTree;

void BuildTree(vector<int>& a, int Vertex, int LeftPos, int RightPos)

{

if (LeftPos == RightPos)

SegTree[Vertex] = a[LeftPos];

else

{

int Middle = (LeftPos + RightPos) / 2;

BuildTree(a, 2 * Vertex, LeftPos, Middle);

BuildTree(a, 2 * Vertex + 1, Middle + 1, RightPos);

SegTree[Vertex] = SegTree[2 * Vertex] + SegTree[2 * Vertex + 1];

}

}

int Summa(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return 0;

if ((Left == LeftPos) && (Right == RightPos))

return SegTree[Vertex];

int Middle = (LeftPos + RightPos) / 2;

return Summa(2 * Vertex, LeftPos, Middle, Left, min(Right, Middle)) + Summa(2 * Vertex + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right);

}

void update(int Vertex, int LeftPos, int RightPos, int Position, int NewValue)

{

if (LeftPos == RightPos)

SegTree[Vertex] = NewValue;

else

{

int Middle = (LeftPos + RightPos) / 2;

if (Position <= Middle) update(2 * Vertex, LeftPos, Middle, Position, NewValue);

else update(2 * Vertex + 1, Middle + 1, RightPos, Position, NewValue);

SegTree[Vertex] = SegTree[2 * Vertex] + SegTree[2 * Vertex + 1];

}

}

vector<int> v;

int n, q, i, d, p, f, t;

char c;

int main(void)

{

cin >> n >> q;

v.resize(n + 1);

SegTree.resize(4 * n + 1);

for (i = 1; i <= n; i++)

cin >> v[i];

BuildTree(v, 1, 1, n);

for (i = 0; i < q; i++)

{

cin >> c;

if (c == '=')

{

cin >> p >> d;

update(1, 1, n, p, d);

}

else

{

cin >> f >> t;

cout << Summa(1, 1, n, f, t) << endl;

}

}

return 0;

}

Algorithm realization – class

#include <cstdio>

#include <vector>

#define MAX 500000

using namespace std;

class SegmentTree

{

public:

vector<int> SegTree;

int len;

SegmentTree(int n)

{

len = n;

SegTree.resize(4*n);

}

SegmentTree(vector<int> &v)

{

len = (int) v.size();

SegTree.resize(4*len);

BuildTree(v,1,0,len-1);

}

void BuildTree(vector<int>&a, int v, int tl, int tr)

{

if (tl == tr) SegTree[v] = a[tl];

else

{

int tm = (tl + tr) / 2;

BuildTree(a, v*2, tl, tm);

BuildTree(a, v*2+1, tm+1, tr);

SegTree[v] = SegTree[v*2] + SegTree[v*2+1];

}

}

int Summa(int Left, int Right)

{

return Summa(1,0,len-1,Left,Right);

}

int Summa(int v, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return 0;

if ((Left == LeftPos) && (Right == RightPos)) return SegTree[v];

int Middle = (LeftPos + RightPos) / 2;

return Summa(v*2, LeftPos, Middle, Left, min(Right,Middle)) +

Summa(v*2+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

void update(int Position, int NewValue)

{

update(1,0,len-1,Position,NewValue);

}

void update(int v, int LeftPos, int RightPos,

int Position, int NewValue)

{

if (LeftPos == RightPos) SegTree[v] = NewValue;

else

{

int Middle = (LeftPos + RightPos) / 2;

if (Position <= Middle)

update (v*2, LeftPos, Middle, Position, NewValue);

else

update (v*2+1, Middle+1, RightPos, Position, NewValue);

SegTree[v] = SegTree[v*2] + SegTree[v*2+1];

}

}

};

vector<int> v;

int n, q, i, j, d, f, t;

char c;

int main(void)

{

scanf("%d %d\n",&n,&q);

v.resize(n+1);

for(i = 1; i <= n; i++) scanf("%d",&v[i]); scanf("\n");

SegmentTree s(v);

for(j = 0; j < q; j++)

{

scanf("%c ",&c);

if (c == '=')

{

scanf("%d %d\n",&i,&d);

s.update(i,d);

} else

{

scanf("%d %d\n",&f,&t);

printf("%d\n",s.Summa(f,t));

}

}

return 0;

}

Algorithm realization – dynamic memory allocation new / delete

#include <cstdio>

#include <algorithm>

using namespace std;

int *SegTree;

void BuildTree(int *a, int Vertex, int LeftPos, int RightPos)

{

if (LeftPos == RightPos)

SegTree[Vertex] = a[LeftPos];

else

{

int Middle = (LeftPos + RightPos) / 2;

BuildTree(a, 2*Vertex, LeftPos, Middle);

BuildTree(a, 2*Vertex+1, Middle+1, RightPos);

SegTree[Vertex] = SegTree[2*Vertex] + SegTree[2*Vertex+1];

}

}

int Summa(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return 0;

if ((Left == LeftPos) && (Right == RightPos))

return SegTree[Vertex];

int Middle = (LeftPos + RightPos) / 2;

return Summa(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)) +

Summa(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

void update(int Vertex, int LeftPos, int RightPos,

int Position, int NewValue)

{

if (LeftPos == RightPos)

SegTree[Vertex] = NewValue;

else

{

int Middle = (LeftPos + RightPos) / 2;

if (Position <= Middle)

update (2*Vertex, LeftPos, Middle, Position, NewValue);

else

update (2*Vertex+1, Middle+1, RightPos, Position, NewValue);

SegTree[Vertex] = SegTree[2*Vertex] + SegTree[2*Vertex+1];

}

}

int n, q, i, j, d, f, t;

char c;

int main(void)

{

scanf("%d %d\n",&n,&q);

int *v = new int[n+1];

for(i = 1; i <= n; i++)

scanf("%d",&v[i]);

scanf("\n");

SegTree = new int[4*n];

BuildTree(v,1,0,n);

delete[] v;

for(j = 0; j < q; j++)

{

scanf("%c ",&c);

if (c == '=')

{

scanf("%d %d\n",&i,&d);

update(1,0,n,i,d);

} else

{

scanf("%d %d\n",&f,&t);

printf("%d\n",Summa(1,0,n,f,t));

}

}

delete[] SegTree;

return 0;

}